% Section~\ref{s:immutability} introduces the rich concept of immutability and its variations.

\section{What is Immutability?}
\label{s:immutability}

An immutable
program component remains the same over time.  Equivalently, changes to
an immutable program component are forbidden.
%% MDE: This is not true for abstract immutability and benevolent side
%% effects, such as if the field isn't part of the abstract state or the
%% change does not affect the abstract value.
% In the object-oriented context, assignment of a field is considered a
% change to the containing object.

An immutable object (Section~\ref{s:immutable-objects}) never changes.  By
contrast, a read-only reference (Section~\ref{s:readonly-references})
cannot be used for mutation, but the referred-to object might change via
other references.  Assignment of fields/variables
(Section~\ref{s:immutability-and-assignment}) is not a mutation of the
referred-to object but is
sometimes confused with it.

Currently, there is no support in Java (or any mainstream OO language) to
express and check object immutability or read-only references.  Rather,
programmers must use external tools that add these capabilities, or else
resort to manual inspection.


% In this section we discuss the concept of immutability. There are
% many parts of an object-oriented system that can be made
% immutable: entire classes, individual objects, the references
% between objects, pure methods, method parameters or individual
% variables and fields. We now discuss the advantages and
% disadvantages of making each of these parts ``read-only'' and
% point to existing work that either fully or partially achieves the
% desired effect.


% Note this Oracle tutorial on "A Strategy for Defining Immutable Objects":
% http://download.oracle.com/javase/tutorial/essential/concurrency/imstrat.html

\subsection{Immutable objects}
\label{s:immutable-objects}

An \emph{immutable
  object}~\cite{zibin:2010:oigj,oestlund:2008:oui} cannot be
modified.
%% MDE: As above, this is already making an assumption about what version
%% of immutability is being used.  This is too restrictive.  Besides, we
%% have just said that immutability is hard to define, but we haven't yet
%% defined it, so it's silly to start discussing its properties.
% That is, its fields cannot be re-assigned.



When every object of a given class is immutable, then we say the class is
immutable.
Examples of immutable classes in
Java~\cite{gosling:2005:java} include \code{String} and most
subclasses of
\code{Number}\footnote{\code{java.util.concurrent.AtomicInteger}
  is mutable, though.} such as \code{Integer} and
\code{BigDecimal}.  An immutable class contains no mutating methods that
update/modify the receiver; rather, if a different value is required, a client calls
a constructor or producer method that returns a new object.
In addition to not providing mutating methods, all fields must be hidden from clients (e.g. made private).


% No instance of an \emph{immutable class} may
%   be changed; examples in Java~\cite{gosling:2005:java} include \code{String} and most
%   subclasses of \code{Number} such as \code{Integer} and
%   \code{BigDecimal} (an \code{AtomicInteger} can be mutated).
%   \mbox{Java's} type system has no way of expressing or checking class
%   immutability. For example, creating new instance of \code{Integer} below is conceptually equivalent to assigning a value \code{42} to a variable of primitive type \code{int}:

% \begin{java}
% Integer my42 = new Integer(42);
% \end{java}

% \noindent One would not be able to modify the value of the object pointed at by \code{my42} thus producing an immutable object due to instantiating an immutable class in Java.


Even if a class is not immutable, specific objects of that class may be
immutable~\cite{zibin:2010:oigj,oestlund:2008:oui}.
For example, 
some instances of \code{List} in a
given program may be immutable, whereas others can be modified.
%
Here is example Immutability Generic Java
(IGJ)~\cite{zibin:2007:immutability} code that instantiates the
same class \code{LinkedList} as both \textit{mutable} and
\textit{immutable} object:

%\mde{I object strongly to the use of the ugly and unhelpful code highlighting
%  that is used in the paper.  In this example, is ``new'' the very most
%  important symbol in the entire example?  It's the only one that is
%  highlighted.  This is worse than useless.  Either manually highlight what
%  actually matters, or else remove all highlighting.}

\begin{java}
LinkedList<Mutable> lm = new LinkedList<Mutable>();
LinkedList<Immutable> li = new LinkedList<Immutable>();
\end{java}

\noindent
Object \code{lm} can be changed or mutated, for example by adding or
removing elements.  By contrast, \code{li} cannot be changed or
mutated, even though it is implemented by the same \code{LinkedList} code.


\subsection{Read-only references}
\label{s:readonly-references}

%% NB! Use "read-only" spelling everywhere!

A \emph{read-only} reference\footnote{``Reference
  immutability'' is another standard term, but we use ``read-only
  reference'' to avoid potential confusion if a reader mis-interprets
  ``reference immutability'' as stating that the reference itself is
  immutable.  Also see Section~\ref{s:immutability-and-assignment}.}~\cite{BirkaE2004,SkoglundW2001,PechtchanskiS2002,TschantzE2005,KnieselT2001,BoylandNR2001,DietlM2005}
cannot be used to modify its
referent. However, there may exist mutable aliases to the object
elsewhere in the system.  In other words, normal references carry the
privilege to mutate the referent, and read-only references do not.

Usually a read-only reference's type is a supertype of a mutable
reference's type, so a mutable reference can be used in any context in
which a read-only one is legal.  For example, continuing the previous list
example, this is legal:
%
\begin{java}
LinkedList<ReadOnly> lro = lm;
\end{java}
%
Note that \code{lm} is a mutable alias that can be
used to mutate the list.

Since read-only references do not preclude the existence of
mutable aliases, read-only references do not
guarantee object immutability, unless read-only references are combined
with an alias/escape analysis to guarantee that no mutable aliases
to an object exist~\cite{Boyapati2004:PhD,BirkaE2004}.

A \emph{const} pointer in \CC{} is a shallow read-only reference.


\subsubsection{Read-Only Method Parameters}

If a method does not mutate one of its formal parameters, then that formal
parameter can be annotated as read-only.  Then, it is legal to call the method
using a mutable, immutable, or read-only reference as the actual argument.
If a method does mutate a formal parameter, then the method can only be
called by passing in a mutable object as an argument.
The receiver is treated the same as the other formal
parameters.

%* p3, second paragraph of "Read-Only Method Parameters": I found this
%  paragraph very confusing and would recommend deleting it. A
%  read-only semantics is clearly NOT the same as copying the
%  objects. For instance, through a read-only reference, a thread can
%  observe modification made by a concurrent thread, but that is not
%  the case if the object gets copied.

%A programming language that supports
%call-by-value or
%return-by-value~\cite{kernighan:1983:on-pascal,wadler:2003:call-dual}  automatically provides a sort of
%read-only constraint.
%Since the value is copied at the procedure call or return, the
%original copy cannot be modified by the implementation or client,
%respectively. Pass- and return-by-value are typically used for
%values such as primitives and references. Some programming
%languages, such as Pascal and Ada, permit variables to be
%explicitly annotated as in, out, or in/out parameters; this is an
%early and primitive form of compiler-enforced read-only
%annotation.



\subsubsection{Pure Methods}

A \emph{pure} method~\cite{SR05,Rou04,LRZ93,Pea11} has no
externally-visible \textit{side effects}. In other words, calling a pure
method is guaranteed to leave every existing object
in an unchanged state.\footnote{Just as there are multiple varieties of
  immutability, there are multiple varieties of purity.  Different
  definitions forbid all mutations, or permit only mutations of object
  allocated after the method is entered, or permit benevolent side effects
  on previously-existing objects.}
This is a stronger guarantee than asserting that
every method parameter is (deeply) read-only, since it applies to static variables
as well.
For example:

\begin{java}
@Pure
boolean has(String x) {
  for (String i : items) {
    if (x == i) { return true; }
  }
  return false;
}
\end{java}


\subsection{Non-assignability}
\label{s:immutability-and-assignment}

Assignment is a property of a
% reference such as a 
variable:  it indicates whether the
variable is permitted to be reassigned.
Assignment of a variable is unrelated to mutation.  In
particular, no object is mutated in this code:

\begin{java}
  Date myVar = ...;   // local variable
  ...
  myVar = anotherDate;
\end{java}

Assignment of a field is a mutation of the object that
contains the field, but is \emph{not} a mutation of either the object that
was previously in the field or of the object that is subsequently in the
field.
For example, in 
%
\begin{java}
  myClass.itsDate = anotherDate;
\end{java}
%
no \code{Date} object has been mutated.

The \kw{final} keyword in Java~\cite{gosling:2005:java} prohibits
assignment but not mutation.  In the following example, the
variable \code{v} is declared \kw{final} and thus it cannot be reassigned
after the declaration, though its value can be mutated:
%
\begin{java}
  final Foo v = new Foo();  // local variable
  ...
  v = new Foo();  // compile-time error: assignment is forbidden
  v.mutate();     // OK: mutation is permitted
\end{java}
% %
% This allows final variables to be captured safely by, e.g.,
% anonymous classes. As the value bound to the final name will never
% change the compiler can copy the value, and the life time of the
% outer scope (stack) is of no concern. However, just like read-only
% references, the actual object the variable might point to (a
% \code{Foo} instance in this case) is not prevented from
% changing --- supporting object immutability would enforce that
% properly.


\subsection{Deep vs.\ shallow immutability; abstract vs.\ concrete immutability}

When specifying an immutability property, it is necessary to state whether
the property is deep or shallow, and which fields of the object's
representation are relevant.

Immutability and read-only references may be deep or shallow, depending on
whether transitively-referred to objects are also required to be immutable.
In deep immutability, it is forbidden not only to re-assign an object's
fields, but also to mutate them.  In shallow immutability, it is forbidden
to re-assign an object's fields, but permitted to mutate them.  Consider
the following example:

\begin{java}
class C {
  D f;
}
class D {
  int x;
}

C<Immutable> myC = ...;
...
myC.f = otherD; // illegal under both deep and shallow immutability
myC.f.x++;      // legal under shallow immutability, illegal under deep
\end{java}

Most often, a client desires a deep rather than a shallow immutability
guarantee. An OO program's representation of some object or concept in the
real world often spans multiple objects in the program.  As a simple
example, a list may be represented by many \code{Link} objects connected in
a linked list.  A client does not know or care about the specific data
representation, but wants a guarantee of immutability of the abstract value
that the concrete data represents.

An orthogonal axis of immutability is which fields should be considered as
protected by the immutability guarantee.
A \emph{benevolent side effect} is one that changes an object's representation,
but does not change the object's abstract value.  A common example is
filling in a field that caches a value.  Another example is the
move-to-front optimization that speeds up looking up elements in a set that
is represented as a list.
Thus, it is possible that a change to an object's representation is
\emph{not} a change to the object's abstract value.

Similarly, just like with ownership-like schemes~\cite{noble:1998:flap}, it might make sense to make only part of an object deeply immutable (e.g. the fields specific to its \textit{representation}) while keeping the other fields mutable. For example, an immutable list might contain mutable elements.

Most often, a client is concerned with the abstract value rather than
details of the object's representation such as cached values or the order
of objects in a set.  However, reasoning about low-level
properties such as interactions with the memory system may require a
guarantee of \emph{representation immutability} rather
than \emph{abstract immutability}.


%%% Local Variables: 
%%% TeX-command-default: "PDF"
%%% End: 

% LocalWords:  BigDecimal lm li mis ReadOnly const JPure boolean assignability
% LocalWords:  myVar anotherDate myClass itsDate myC otherD dribs OO IGJ
%  LocalWords:  lro Foo
